package april;

import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-4-22 20:42
 * @description：
 * @modified By：
 * @version:
 */

public class April22 {
    public class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode(int x) { val = x; }
  }
    /**
     * create by: 睚雪
     * description: 广度搜索 每一层搜索到的最后一个就最右边的节点 层次遍历
     * create time: 2020-4-22 20:43
     * @params [root]
     * @return java.util.List<java.lang.Integer>
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        int count = 0; //当前所在的层数 当需要进入左子树时会有用
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);

                }
                if (node.right!=null){
                    queue.offer(node.right);

                }
                if(i==size-1){ //到了最后一个
                    list.add(node.val);
                }
            }
        }
        return list;
    }
    /**
     * create by: 睚雪
     * description: 深度搜索 每次优先遍历右子树 就可以保证每一层第一次访问到的都是最右边的节点
     * create time: 2020-4-22 21:21
     * @params [root]
     * @return java.util.List<java.lang.Integer>
     */
    public List<Integer> rightSideView2(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        dfs(root,0,list);
        return list;
    }
    public void dfs(TreeNode node,int depth,List<Integer> list){
        if(node!=null){
            if(depth==list.size()){
                list.add(node.val);
            }
            dfs(node.right,depth+1,list);
            dfs(node.left,depth+1,list);
        }
    }
}
